package util;

import java.util.*;

/**
 * Created by liuwei on 2018/1/12.
 */
public class Solution {


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0, append = 0, left = 0;
        ListNode root = new ListNode(0);
        ListNode result = root;
        while (l1 != null || l2 != null) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            sum = v1 + v2 + append;
            append = sum / 10;
            left = sum % 10;
            ListNode cursor = new ListNode(left);
            result.next = cursor;
            result = cursor;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;

        }
        if (append > 0) {
            ListNode cursor = new ListNode(append);
            result.next = cursor;
        }

        return root.next;

    }

    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int len = L.length;
        if (len == 0) {
            return list;
        }
        int wordLen = L[0].length();
        Map<String, Integer> wordsMap = new HashMap<String, Integer>();
        for (int i = 0; i < len; i++) {
            int num = 1;
            if (wordsMap.get(L[i]) != null) {
                num += wordsMap.get(L[i]);
            }
            wordsMap.put(L[i], num);
        }
        int slen = S.length();
        int max = slen - wordLen + 1;
        for (int i = 0; i < wordLen; i++) {
            Map<String, Integer> numMap = new HashMap<String, Integer>();
            int count = 0;
            int start = i;
            for (int end = start; end < max; end += wordLen) {
                String tempStr = S.substring(end, end + wordLen);
                if (!wordsMap.containsKey(tempStr)) {
                    numMap.clear();
                    count = 0;
                    start = end + wordLen;
                    continue;
                }
                int num = 1;
                if (numMap.containsKey(tempStr)) {
                    num += numMap.get(tempStr);
                }
                numMap.put(tempStr, num);
                if (num <= wordsMap.get(tempStr)) {
                    count++;
                } else {
                    while (numMap.get(tempStr) > wordsMap.get(tempStr)) {
                        tempStr = S.substring(start, start + wordLen);
                        numMap.put(tempStr, numMap.get(tempStr) - 1);
                        if (numMap.get(tempStr) < wordsMap.get(tempStr)) {
                            count--;
                        }
                        start += wordLen;
                    }
                }
                if (count == len) {
                    list.add(start);
                    tempStr = S.substring(start, start + wordLen);
                    numMap.put(tempStr, numMap.get(tempStr) - 1);
                    count--;
                    start += wordLen;
                }
            }
        }
        return list;
    }


    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        //排序有利于判断重复值
        Arrays.sort(nums);
        //深度优先算法
        dfs(nums, used, list, res);
        return res;
    }

    public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res) {
        //如果结果长度和输入长度相等，则添加进结果集
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 如果该元素已经被使用过，则继续遍历
            if (used[i]) continue;
            //下一个重复值只有在前一个重复值被使用的情况下才可以使用
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) continue;
            used[i] = true;
            list.add(nums[i]);
            dfs(nums, used, list, res);
            used[i] = false;
            list.remove(list.size() - 1);
        }
    }

    public void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix.length; j++) {
                swap(matrix, i, j);
            }
            for (int j = 0; j < matrix.length; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length - 1 - i];
                matrix[i][matrix.length - 1 - i] = tmp;
            }
        }
    }

    void swap(int[][] matrix, int i, int j) {
        int tmp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = tmp;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            String sorted = sorted(str);
            if (map.keySet().contains(sorted)) {
                List<String> list = map.get(sorted);
                list.add(str);
                map.put(sorted, list);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(sorted, list);
            }
        }
        return new ArrayList<>(map.values());
    }

    public String sorted(String str) {
        char[] c = str.toCharArray();
        for (int i = 0; i < c.length - 1; i++) {
            for (int j = i + 1; j < c.length; j++) {
                if (c[i] > c[j]) {
                    char tmp = c[i];
                    c[i] = c[j];
                    c[j] = tmp;
                }
            }
        }
        return String.valueOf(c);
    }


    public ListNode rotateRight(ListNode head, int k) {

        if (head == null) return null;
        int n = 0;
        ListNode cur = head;
        while (null != cur.next) {
            n++;
            cur = cur.next;
        }
        cur.next = head;
        int m = n - k;
        for (int i = 0; i < m; i++) {
            cur = cur.next;
        }
        ListNode res = cur.next;
        cur.next = null;
        return res;
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        obstacleGrid[0][0] = 1;
        if (m == 1 || n == 1) {
            return 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }

        return dp[m - 1][n - 1];

    }

    public boolean isNumber(String s) {
        boolean flag = false;
        boolean eFlag = false;
        boolean floatFlag = false;
        s = s.trim();
        int len = s.length();
        if (s.startsWith("+") || s.startsWith("-")) {
            s = s.substring(1, len);
            len--;
        }

        //是否包含e
        if (s.indexOf('e') > 0) {
            String left = s.substring(0, s.indexOf('e'));
            String right = s.substring(s.indexOf('e') + 1, len);

            for (int i = 0; i < left.length(); i++) {
                char c = left.charAt(i);
                if ('0' <= c && c <= '9') {
                    flag = true;
                } else if (!floatFlag && c == '.' && !left.equals(".")) {
                    floatFlag = true;
                } else {
                    return false;
                }
            }
            if (right.startsWith("+") || right.startsWith("-")) {
                right = right.substring(1, right.length());

            }
            if (right.length() == 0) return false;
            for (int i = 0; i < right.length(); i++) {
                char c = right.charAt(i);
                if ('0' <= c && c <= '9') {
                    flag = true;
                } else {
                    return false;
                }
            }
        } else {
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if ('0' <= c && c <= '9') {
                    flag = true;
                } else if (i != 0 && i != len - 1 && !eFlag && c == 'e') {
                    eFlag = true;
                } else if (!floatFlag && c == '.') {
                    floatFlag = true;
                } else {
                    return false;
                }
            }
        }
        return flag;
    }

    public int mySqrt(int x) {
        long low = 0;
        long up = x;
        while (low <= up) {
            long mid = (low + up) / 2; // 取中间值mid，在此处如果改为位运算居然使程序变慢了！
            long square = mid * mid;
            if (x == square) return (int) mid;  // 目标值等于mid处平方，提前退出循环出口
            else if (x > square) low = mid + 1;  // 目标值大于mid处平方，在开区间(mid, up]中找，下界low的值调整为mid-1
            else up = mid - 1;               // 目标值小于mid处平方，在开区间[low, mid)中找，上界up的值调整为mid+1
        }
        return (int) up;
    }




    public static void main(String[] args) {
        String s = "1.5e89e0";
        int len = s.length();
        String left = s.substring(0, s.indexOf('e'));
        String right = s.substring(s.indexOf('e') + 1, len);
        System.out.println(left);
        System.out.println(right);
//        System.out.println(new Solution().isNumber("0"));



    }


}

